﻿#region Copyright information
// 
// Copyright © 2012-2013 Yongkee Cho. All rights reserved.
// 
// This code is a part of the SubnetworkToolkit and governed under the terms of the
// GNU Lesser General  Public License (LGPL) version 2.1 which accompanies this distribution.
// For more information on the LGPL, please visit http://bol.codeplex.com/license.
// 
// - Filename: SubnetGenome.cs
// - Author: Yongkee Cho
// - Email: yongkeecho@outlook.com
// - Date Created: 2013-01-30 2:55 PM
// - Last Modified: 2013-01-30 3:21 PM
// 
#endregion
using System;
using System.Collections.Generic;
using System.Linq;
using BOL.Algorithms.Optimization.EvolutionaryAlgorithms;
using BOL.Linq;
using BOL.Linq.Descriptive;

namespace SubnetworkToolkit.GeneticAlgorithmSearch
{
    public sealed class SubnetGenome : GenomeBase<int>, IEquatable<SubnetGenome>
    {
        #region Private variables

        private readonly IDictionary<int, List<int>> _dictionary;
        private readonly IDictionary<int, double> _statistics;
        private readonly int _minNodes;
        private readonly int _maxNodes;
        private readonly IList<int> _bypass;
        private readonly double _mean;
        private readonly double _stdDev;

        #endregion

        #region public properties

        public List<int> Ids { get; private set; }

        #endregion

        #region Constructor

        public SubnetGenome(Random random, IDictionary<int, List<int>> dictionary, IDictionary<int, double> statistics, List<int> ids, int minNodes, int maxNodes, IList<int> bypass, double mean, double stdDev)
            : base(random)
        {
            if (random == null)
                throw new ArgumentNullException("random");
            if (dictionary == null)
                throw new ArgumentNullException("dictionary");
            if (statistics == null)
                throw new ArgumentNullException("statistics");
            if (ids == null)
                throw new ArgumentNullException("ids");

            _dictionary = dictionary;
            _statistics = statistics;
            Ids = ids;
            _minNodes = minNodes;
            _maxNodes = maxNodes;
            _bypass = bypass;
            _mean = mean;
            _stdDev = stdDev;
        }

        #endregion

        #region IGenome<TGene> implementation

        protected override IGenome<int> Clone()
        {
            return new SubnetGenome(Random, _dictionary, _statistics, Ids.Select(x => x).ToList(), _minNodes, _maxNodes, _bypass, _mean, _stdDev);
        }

        private IEnumerable<int> GetNeighbors(IList<int> ids)
        {
            return ids.SelectMany(x => _dictionary[x]).Distinct().Except(ids);
        }

        public override void Evaluate()
        {
            var k = Ids.Count;
            Fitness = k > 0 ? (Ids.Except(_bypass).Sum(x => Math.Abs(_statistics[x])) - k * _mean) / k : 0.0;
        }

        public override IGenome<int> Offspring()
        {
            var seed = 0;
            while (seed != 0)
                seed = _dictionary.FirstOrDefault(Random).Key;
            
            return Offspring(seed);
        }

        public SubnetGenome Offspring(int seed)
        {
            if (!_dictionary.ContainsKey(seed))
                throw new ArgumentOutOfRangeException("seed");

            var ids = new List<int> { seed };

            //// 
            //var neighbors = new List<int>();
            //Search(seed, ref ids, ref neighbors);

            var numberOfNodes = Random.Next(_minNodes, _maxNodes);
            var neighbors = GetNeighbors(ids);

            while (ids.Count < numberOfNodes && neighbors.Any())
            {
                ids.Add(neighbors.OrderByRandom(Random).First());
                neighbors = GetNeighbors(ids);
            }
            return new SubnetGenome(Random, _dictionary, _statistics, ids, _minNodes, _maxNodes, _bypass, _mean, _stdDev);
        }

        public void Grow()
        {
            var neighbors = GetNeighbors(Ids);

            Ids.Add(neighbors.OrderByRandom(Random).First());
        }

        private void Search(int prev, ref List<int> ids, ref List<int> neighbors)
        {
            var newNeighbors = neighbors.Concat(_dictionary[prev]).Except(ids).ToList();

            if (newNeighbors.Any())
            {
                var current = newNeighbors.ArgMax(x => Math.Abs(_statistics[x]));
                ids.Add(current);

                if (ids.Count < _minNodes)
                    Search(current, ref ids, ref neighbors);
            }
        }

        #endregion

        #region Crossover operations

        public override void Crossover(IGenome<int> other)
        {
            Crossover(other as SubnetGenome);
        }

        private void Crossover(SubnetGenome other)
        {
            var commonNodes = Ids.Intersect(other.Ids).ToList();
            if (commonNodes.Any()) // if common nodes exist,
            {
                var commonEdges = GetCommonEdges(commonNodes).ToList();
                if (commonEdges.Any()) // if common edges exist,
                {
                    // for each common edge ordered by random
                    foreach (var commonEdge in commonEdges.OrderByRandom(Random))
                    {
                        // remove nodes of the common edge from original list
                        var dad = Ids.Select(x => x).Except(commonEdge).ToList();
                        var mom = other.Ids.Select(x => x).Except(commonEdge).ToList();

                        // if # connected components is more than two,
                        List<int> dadFirst, dadSecond, momFirst, momSecond;
                        if (GetConnectedComponents(dad, out dadFirst, out dadSecond) > 1 &&
                            GetConnectedComponents(mom, out momFirst, out momSecond) > 1)
                        {
                            var d = dadFirst.Any(x => _dictionary[x].Contains(commonEdge[0]));
                            var m = momFirst.Any(x => _dictionary[x].Contains(commonEdge[0]));

                            dadFirst.AddRange(commonEdge);
                            dadSecond.AddRange(commonEdge);

                            // do crossover operation
                            if (d ^ m) // d1:0 & m1:1 || d1:1 & m1:0
                            {
                                dadFirst.AddRange(momFirst);
                                dadSecond.AddRange(momSecond);
                            }
                            else
                            {
                                dadFirst.AddRange(momSecond);
                                dadSecond.AddRange(momFirst);
                            }

                            // update genome
                            Ids = dadFirst.Distinct().ToList();
                            other.Ids = dadSecond.Distinct().ToList();

                            return;
                        }
                    }
                }
            }
            else // if no common node exists,
            {
                var commonNeighbors = GetNeighbors(Ids).Intersect(GetNeighbors(other.Ids)).ToList();
                if (commonNeighbors.Any()) // if common neighbors exist,
                {
                    // gets most connected common neighbor
                    var crossoverId = commonNeighbors.OrderByDescending(x => _dictionary[x].Count).First();

                    // one takes all
                    Ids.Add(crossoverId);
                    Ids.AddRange(other.Ids);

                    // other none
                    other.Ids = new List<int>();
                }
            }
        }

        private IEnumerable<int[]> GetCommonEdges(IEnumerable<int> commonVertices)
        {
            var cv = commonVertices.ToList();
            return cv.SelectMany(x => _dictionary[x].Where(cv.Contains).Select(y => new[] {x, y}));
        }

        private int GetConnectedComponents(IList<int> vertices, out List<int> first, out List<int> second)
        {
            if (vertices.Count > 0)
            {
                var seed = vertices.FirstOrDefault(Random);
                first = new List<int>();
                Condense(ref vertices, ref first, seed);
                second = vertices.ToList();
                
                return second.Count > 0 ? 2 : 1;
            }

            first = new List<int>();
            second = new List<int>();

            return 0;
        }

        private void Condense(ref IList<int> vertices, ref List<int> component, int seed)
        {
            vertices.Remove(seed);
            component.Add(seed);

            foreach (var c in _dictionary[seed].Intersect(vertices))
                Condense(ref vertices, ref component, c);
        }

        #endregion

        #region Mutation operation

        public override void Mutate(double mutationRate)
        {
            var numberOfGenesToBeMutated = (int)Math.Round(_dictionary.Count * mutationRate);

            for (var i = 0; i < numberOfGenesToBeMutated; i++)
                Mutate();
        }

        private void Mutate()
        {
            var numberOfNodes = Ids.Count;
            
            if (numberOfNodes >= _maxNodes)
                DestructiveMutate();
            else if (numberOfNodes < _minNodes)
                ConstructiveMutate();
            else
            {
                var rand = Random.NextDouble();

                if (rand <= 0.25)
                    DestructiveMutate();
                else if (rand > 0.25 && rand <= 0.5)
                    ConstructiveMutate();
                else
                    SwapMutate();
            }
        }

        private void DestructiveMutate()
        {
            var idToDestruct = Ids.Where(i => _dictionary[i].Count == 1).FirstOrDefault(Random);
            if (idToDestruct > 0)
                Ids.Remove(idToDestruct);
        }

        private void ConstructiveMutate()
        {
            var idToConstruct = GetNeighbors(Ids).FirstOrDefault(Random);
            if (idToConstruct > 0)
                Ids.Add(idToConstruct);
        }

        private void SwapMutate()
        {
            DestructiveMutate();
            ConstructiveMutate();
        }
           
        #endregion

        #region IEquatable<SubnetGenome> implementation

        public bool Equals(SubnetGenome other)
        {
            return Ids.SetEquals(other.Ids);
        }

        #endregion

        #region Object overriden

        public override int GetHashCode()
        {
            unchecked
            {
                const int p = 16777619;
                var hash = Ids.Aggregate((int) 2166136261, (current, id) => (current ^ id) * p);

                hash += hash << 13;
                hash ^= hash >> 7;
                hash += hash << 3;
                hash ^= hash >> 17;
                hash += hash << 5;

                return hash;
            }
        }

        public override bool Equals(object other)
        {
            if (other == null)
                throw new ArgumentNullException("other");

            if (!(other is SubnetGenome))
                throw new InvalidCastException("The 'other' argument is not a SubnetGenome object.");

            return Equals(other as SubnetGenome);
        }

        public override string ToString()
        {
            return String.Join(", ", Ids.OrderBy(x => x));
        }

        #endregion
    }
}
